/*
 * 朴素的模式匹配 (应该是和暴力匹配算法Brute-Force差不多)
 */

#include <stdio.h>
#include <string.h>


/*
 * 没完全测试，谨慎使用
 */
int str_index(char *s, char *t, int pos)
{
    if (s == NULL || t == NULL || pos < 0 || pos >= strlen(s))
        return -1;

    int i, j, flag;
    for (i = pos; s[i] != '\0'; ++i) { // 从pos位置开始匹配
        flag = 1;
        for (j = 0; s[i+j] != '\0' && t[j] != '\0'; ++j) {
            if (s[i+j] != t[j]) {
                flag = 0;
                break;
            }
        }

        if (flag == 1 && t[j] == '\0')
            return i-pos;
    }
    
    return -1;
}


/*
 * 第二种实现方法。
 * 参考大话数据结构。
 *
 * 推荐使用这个
 *
 * 规则：
 * 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
 * 1、如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
 * 2、如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
 * 
 * 参考 https://blog.csdn.net/v_july_v/article/details/7041827
 *
 * 最坏情况的时间复杂度为 O((n-m+1)*m)
 */
int str_index_2(char *s, char *t, int pos)
{
    if (s == NULL || t == NULL || pos < 0 || pos >= strlen(s))
        return -1;

    int i = pos; // 从pos位置开始匹配
    int j = 0;
    while (s[i] != '\0' && t[j] != '\0') {
        if (s[i] == t[j]) {
            ++i;
            ++j;
        } else {
            i = i-j+1; // i退回到上次匹配开始的下一位
            j = 0; // j退回到子串的第一位
        }
    }
    if (t[j] == '\0')
        return (i - pos) - j;
    else
        return -1;
}


int main(void)
{
    char *s = "goodgoogle";
    char *t = "google";

    int i = str_index_2(s, t, 0);
    printf("i=[%d]\n", i);

    return 0;
}
